package com.tgy.algorithm.base._斐布拉契数推广;

public class _斐布拉契数 {


    public static int fib(int n) {

        if (n == 1 || n == 2) {
            return 1;
        }

        /**
         * 1,1 单位矩阵
         * [
         *    [1,0]
         *    [0,1]
         * ]
         */

        int[][] sum = {{1,0},{0,1}};

        /**
         *
         * [F(n),F(n-1)] = [1,1] * ([[1,1],[1,0]]) ^ (n - 2)
         *
         */
        int[][] unit = {{1,1},{1,0}};

        int index = 0;
        n = n  - 2;
        while (n > 0) {
            int pIndex = 1 << (index++);
            if ((n & pIndex) != 0) {
                sum = maxtrix(sum,unit);
            }

            unit = maxtrix(unit,unit);
            n = n ^ pIndex;
        }

        // [F(n),F(n-1)] =  [1,1] * sum;
        return sum[0][0] + sum[1][0];
    }

    public static int[][] maxtrix(int[][] one, int[][] two) {

        int row = one.length;
        int col = two[0].length;
        int[][] ret = new int[row][col];

        int sum;
        for (int i = 0; i < row; i++) {
            int[] rows = one[i];
            for (int j = 0; j < col; j++) {
                sum = 0;
                for (int k = 0; k < rows.length; k++) {
                    sum += rows[k] * two[k][j];
                }
                ret[i][j] = sum;
            }
        }

        return ret;
    }

    public static long index(long n) {

        /**
         *
         * 2^14
         *  1010
         * 2
         */
        long base = 2;
        long sum = 1;
        int index = 0;
        while (n > 0) {
            long val = 1 << index;
            long flag = n & val;
            if (flag != 0) {
                sum = sum * base;
            }
            base = base*base;
            index++;
            n = n ^ val;
        }

        return sum;
    }

    public static void main(String[] args) {
//        int[][] one = {{1,3,2},{2,1,1}};
//        int[][] two = {{1,1},{2,2},{1,1}};
//        int[][] maxs = maxtrix(one, two);
//        for (int[] max : maxs) {
//            System.out.println(Arrays.toString(max));
//        }

//        long res = index(14);
//        System.out.println(res);

        int fib = fib(20);
        System.out.println(fib);
    }
}
